Turing Machine

图灵机定义

图灵机的运行规则

图灵机由 有穷状态控制器 和带组成，两者之间通过带头进行操作
控制器在每步完成两个功能
1. 让控制器进入新状态（和 DFA / NFA 类似）
2. 在当前扫描的带方格中填入一个符号 / 把读写头向左或向右移动一个带方格

图灵机的符号标示

A Turing Machine is 5-tuple $M = (K, Σ, δ, s, H)$

$K$ : a finite set of state
$Σ$ : an alphabet (containing $▹$ and $⊔$ )
$s$ : initial state
$H \subseteq K$ : a set of halting state
$δ$ : transition function
- $(K - H) \times Σ \to K \times (Σ \cup {\leftarrow, \to})$
  - $K - H$ is current state
  - $Σ$ is symbols
  - $K$ is next state
  - $(Σ \cup {\leftarrow, \to})$ is writing or moving
- it satisfying
  - for any $q \in K - H$ , $δ (q, ▹) = (p, \to)$ for some $p \in K$
  - for any $q \in K - H$ , any $a \in Σ$ , if $δ (q, a) = (p, b)$ , $b \neq ▹$

图灵机的当前状态可表示为 $K \times ▹ (Σ - {▹})^{*} \times ((Σ - {▹})^{*} (Σ - {▹, ⊔}) \cup {e})$

带内容的简化记号 $\underset{―}{}$ ： $w \underset{―}{a} u$ 表示 $(q, w a, u)$ 里的带内容

A configuration is a member of $K \times ▹ (Σ - {▹})^{*} \times ((Σ - {▹})^{*} (Σ - {▹, ⊔}) \cup {e})$ , and we say $(q_{1}, ▹ w_{1} a_{1} u_{1}) ⊢_{M} (q_{2}, ▹ w_{2} a_{2} u_{2})$ if

writing: $δ (q_{1}, a_{1}) = (q_{2}, a_{2})$ , $a_{2} \in Σ - {▹}$ , $w_{2} = w_{1}$ , $u_{2} = u_{1}$
moving left: $δ (q_{1}, a_{1}) = (q_{2}, \leftarrow)$ , $w_{1} = w_{2} a_{2}$ and $u_{2} = a_{1} u_{1}$
moving right: $δ (q_{1}, a) = (q_{2}, \to)$ , $w_{2} = w_{1} a_{1}$ , $u_{1} = a_{2} u_{2}$
Similarly, we have the $(q_{1}, ▹ w_{1} a_{1} u_{1}) ⊢_{M}^{*} (q_{2}, ▹ w_{2} a_{2} u_{2})$ .

图灵机的几种表示形式

formal definition $M = (K, Σ, δ, s, H)$
Implemental-level description(diagram)
high-level description "pseudo code"

图灵机的记号

基本机器
- 写符号机 $a$ ：对每个 $b \in Σ - {▹}$ ， $δ (s, b) = (h, a)$
- 移带头机 $L$ , $R$
组合机器：直到上一台机器停机为止才应用从前一台机器到后一台机器的连接
```
flowchart LR
M1 --a--> M2
M1 --b--> M3
```
更多机器
- $R \to R$ : can becomes simply $R R$ , or even $R^{2}$
- $R_{⊔}$ : 寻找当前扫描方格右方的第一个空格方格
- $L_{⊔}$ : 寻找当前扫描方格左方的第一个空格方格
- $R_{\overset{―}{⊔}}$ : 寻找当前扫描方格右方的第一个非空格方格
- $L_{\overset{―}{⊔}}$ : 寻找当前扫描方格左方的第一个非空格方格
- $C$ : transforms $\underset{―}{⊔} w ⊔$ into $⊔ w ⊔ w \underset{―}{⊔}$ , where $w$ contains no blanks.
- $S_{\to}$ : $⊔ w \underset{―}{⊔}$ into $⊔ ⊔ w \underset{―}{⊔}$ , where $w$ contains no blanks.

what is overline

\overset{―}{a}

If $a \in Σ$ is any symbol, we can sometimes eliminate multiple arrows and labels by using $\overset{―}{a}$ to mean "any symbol except a."

图灵机的应用

Recoganize Language 识别语言

Let $M = (K, Σ_{0}, Σ, δ, s, {y, h})$ be a TM, we say $M$ decides a language $L \subseteq Σ_{0}^{*}$ if

for every $w \in L$ , $(s, ▹ \underset{―}{⊔} w) ⊢_{M}^{*} (y, \dots)$ , $M$ accepts $w$
for every $w \in L$ , $(s, ▹ \underset{―}{⊔} w) ⊢_{M}^{*} (n, \dots)$ , $M$ rejects $w$

A language $L$ is recursive(decidable) if it is decided by some Turing Machine.

半判定 semidecide and L(M)

$L (M) = {w \in Σ_{o}^{*} : (s, ▹ \underset{―}{⊔} w) ⊢_{M}^{*} (h, \dots) f o r s o m e h \in H}$
we can said that M semidecides L(M)

Theorem: If

L

is recurisive,

L

must be recursively enumerable

Theorem: If

L

is recurisive,

\overset{―}{L}

must be recursive

graph 
	s(semidecide) --> re(recursively enumerable)
	re --> s
	d(decide) --> rl(recurive language)
	rl --> d
	rl --充分条件--> re
	subgraph 决定 
		s
		d
	end

Prove that

A

= {"

M

M

is a TM that halts on some input} is recursive enumerable

Let $Σ^{*} = {s_{1}, s_{2}, s_{3}, \dots}$ (sort by length)

Construct $M_{A}$ = on input "M"

for i = 1, 2, 3, ...
- for s = $s_{1}$ , $s_{2}$ , $s_{3}$ , ...
  - run $M$ on $s$ for $i$ steps
  - if $M$ halts on $s$ within $i$ steps
    - halt

PS: 这是一种常用的技巧：限制每次的运行步数，不断扩散

Compute function 表示函数

Let $M = (K, Σ, δ, s, {h})$ be a Turing machine, let $Σ_{0} \subseteq Σ - {⊔, ▹}$ be an alphabet, and let $w \in Σ_{0}^{*}$ . Suppose that M halts on input $w$ , and that $(s, ▹ \underset{―}{⊔} w) ⊢_{M}^{*} (h, ▹ \underset{―}{⊔} y)$ for some $y \in Σ_{0}^{*}$ . Then $y$ is called the output of $M$ on input $w$ , and is denoted $M (w)$ .
Now let $f$ be any function from $Σ_{0}^{*}$ to $Σ_{0}^{*}$ . We say that $M$ computes function $f$ if, for all $w \in Σ_{0}^{*}$ , $M (w) = f (w)$ . A function $f$ is called recursive, if there is a Turing machine $M$ that computes $f$ .

证明 recursive / recursively enumerable / non-recursive / not recursively enumerable 的方法

证明 recursive
1. 定义法：构造对应的 TM
2. 归约法： $A \leq$ known recursive language
证明 recursively enumerable
1. 定义法：构造对应的 TM
2. 归约法： $A \leq$ known recursively enumerable language
证明 non-recursive
1. 归约法：known recursively enumerable language $\leq A$
证明 not recursively enumerable
1. If $A$ and $\bar{A}$ is recursively enumerable, then $A$ is recursive
2. 归约法：known not recursively enumerable language $\leq A$

Prove something about

B

={"

M

M

is a TM halts on every input}

$\bar{B}$ is not recursive enumerable

$H \leq B \Rightarrow \bar{H} \leq \bar{B} \Rightarrow \bar{B}$ is not recursive enumerable

$B$ is not recursive enumerable

try $\bar{H} \leq B$
$\bar{H}$ with input 'M''w', $B$ with input $f (^{'} M^{″} w^{'})$
$M$ does not halt on $w$ iff $f (^{'} M^{″} w^{'})$ halts on every input
Construct $f (^{'} M^{″} w^{'})$ = on input v
- run $M$ on $w$ for $| v |$ steps
- if $M$ halts on $w$ within $| v |$ steps
  - loop(not halts)
- if $M$ does not halts on $w$ within $| v |$ steps
  - halts
Validation
- $M$ not halts on $w$ ⇒ $f$ halts on every input
- $M$ halts on $w$ ⇒ when $| v |$ is long enough, f loop ⇒ $f$ does not halt on every input

拓展图灵机

所有的拓展图灵机都可以等价转换成普通图灵机

multiple tapes
two-way infinite tape
multiple heads
two-dimensional tape
random access
non-determinstic turing machine

Non-determinstic Turing Machine

a non-deterministic Turing Machine (NTM) is 5-tuple $(K, Σ, Δ, s, H)$

A NTM $M$ with input alphabet $Σ_{0}$ semidecides $L \subseteq Σ_{0}^{*}$ if for any $w \in Σ_{0}^{*}$

$w \in L$ iff $(s, ▹ \underset{―}{⊔} w) ⊢_{M}^{*} (h, \dots)$
if $w \in L$ some branch halts
if $w \notin L$ no branch halts

A NTM $M = (K, Σ_{0}, Σ, Δ, s, {y, n})$ with input alphabet $Σ_{0}$ decides a language $L \subseteq Σ_{0}^{*}$ if

there is a natrual number $N$ , depending on $M$ and $w$ such that there is no configuration $C$ satisfying $(s, ▹ \underset{―}{⊔} w) ⊢_{M}^{N} C$
$w \in L$ iff $(s, ▹ \underset{―}{⊔} w) ⊢_{M}^{*} (y, \dots)$

Theorem: A NTM can be simulated by a DTM